package data.structure.binarytree;

import com.alibaba.fastjson.JSON;

import java.util.Arrays;
import java.util.List;

/**
 * @ClassName: BinarySearchTree
 * @Description:
 * @Author: qiaopengxiang
 * @Date: 2022/5/8 21:59
 */
public class BinarySearchTree {
    private NodeTree tree;

    public static void main(String[] args) {
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        List<Integer> arrays = Arrays.asList(5,4,5,9,3,6,10);
        arrays.forEach(integer -> binarySearchTree.insert(integer));
//        NodeTree.preOrder(binarySearchTree.tree);
//        Integer integer = binarySearchTree.find(1);
//        System.out.println("二叉树查找:".concat(integer+""));
       // binarySearchTree.delete(9);
        System.out.println(JSON.toJSONString(binarySearchTree.tree));

    }


    public void  del(int data){
        NodeTree p = tree;//要删除的节点，初始化给一个根节点
        NodeTree pp = null;//要删除节点的父节点
        //找出需要删除的节点
        while (p!=null && p.data != data){
            pp = p;
            if (data>p.data){
                p = p.right;
            }else {
                p = p.left;
            }
        }
        if (p == null){
            return;
        }

       //如果一个节点还有两个以上子节点，求出右子树最小的左子节点
        if (p.left != null && p.right!=null){
            NodeTree minp = p.right;
            NodeTree minpp = p;
            while (minp.left!=null){
                minpp = minp;
                minp = minpp.left;
            }
            p.data = minp.data;
            p = minp;
            pp = minpp;
        }

        //设置要更新的节点
        NodeTree child = null;
        if (p.left!=null){
            child = p.left;
        }else if(p.right!=null){
            child = p.right;
        }
        //赋值
        if (pp == null){
            tree = child;
        }else if (pp.right==p){
            pp.right = child;
        }else if (pp.left == p){
            pp.left = child;
        }

    }


    /**
     * 删除
     * @param data
     */
    public void delete(int data) {
        // p指向要删除的节点，初始化指向根节点
        NodeTree p = tree;
        // pp记录的是p的父节点
        NodeTree pp = null;
        while (p != null && p.data != data) {
            pp = p;
            if (data > p.data) {
                p = p.right;
            }
            else {
                p = p.left;
            }
        }
        // 没有找到
        if (p == null){ return;}

        // 要删除的节点有两个子节点
        if (p.left != null && p.right != null) {
            // 查找右子树中最小节点
            NodeTree minP = p.right;
            NodeTree minPP = p;
            // minPP表示minP的父节点
            while (minP.left != null) {
                minPP = minP;
                minP = minP.left;
            }
            p.data = minP.data;
            // 将minP的数据替换到p中
            p = minP;
            // 下面就变成了删除minP了
            pp = minPP;
        }

        // 删除节点是叶子节点或者仅有一个子节点
        NodeTree child;
        // p的子节点
        if (p.left != null){ child = p.left;}
        else if (p.right != null) {child = p.right;}
        else {child = null;}

        if (pp == null){ tree = child;}
        // 删除的是根节点
        else if (pp.left == p){ pp.left = child;}
        else {pp.right = child;}
    }

    /**
     * 查找
     * @param data
     * @return
     */
    public Integer find(int data){
        NodeTree p = tree;
        while (p!=null){
            if (data>p.data){
                p = p.right;
            }else if (data<p.data){
                p = p.left;
            }else {
                return data;
            }

        }
        return null;
    }

    /**
     * 新增
     * @param data
     */
    public  void insert(int data){
        if (tree==null){
            tree = new NodeTree(data);
            return;
        }
        NodeTree p = tree;
        while (p!=null){
            if (data>p.data){
                if (p.right==null){
                    p.right = new NodeTree(data);
                    return;
                }
                p = p.right;
            }else {
                if (p.left==null){
                    p.left = new NodeTree(data);
                    return;
                }
                p = p.left;
            }
        }
    }
}
